MySQL 索引是个啥？

索引是什么？

索引的出现其实就是为了提高数据查询的效率，就像书的目录一样。一本 500 页的书，如果你想快速找到其中的某一个知识点，在不借助目录的情况下，那我估计你可得找一会儿。同样，对于数据库的表而言，索引其实就是它的“目录”。

索引的常见模型

索引的出现是为了提高查询效率，但是实现索引的方式却有很多种，所以这里也就引入了索引模型的概念。可以用于提高读写效率的数据结构很多，这里我先给你介绍三种常见、也比较简单的数据结构，它们分别是哈希表、有序数组和搜索树。

我主要从使用的角度，为你简单分析一下这三种模型的区别。

哈希表

哈希表是一种以键-值（key-value）存储数据的结构，我们只要输入待查找的值即 key，就可以找到其对应的值即 Value。哈希的思路很简单，把值放在数组里，用一个哈希函数把 key 换算成一个确定的位置，然后把 value 放在数组的这个位置。

不可避免地，多个 key 值经过哈希函数的换算，会出现同一个值的情况。处理这种情况的一种方法是，拉出一个链表。

假设，你现在维护着一个身份证信息和姓名的表，需要根据身份证号查找对应的名字，这时对应的哈希索引的示意图如下所示：

图中，User2 和 User4 根据身份证号算出来的值都是 N，但没关系，后面还跟了一个链表。假设，这时候你要查 ID_card_n2 对应的名字是什么，处理步骤就是：首先，将 ID_card_n2 通过哈希函数算出 N；然后，按顺序遍历，找到 User2。

需要注意的是，图中四个ID_card_n的值并不是递增的，这样做的好处是增加新的 User 时速度会很快，只需要往后追加。但缺点是，因为不是有序的，所以哈希索引做区间查询的速度是很慢的。

你可以设想下，如果你现在要找身份证号在 [ID_card_X, ID_card_Y] 这个区间的所有用户，就必须全部扫描一遍了。所以，哈希表这种结构适用于只有等值查询的场景，比如 Memcached 及其他一些 NoSQL 引擎。

有序数组

而有序数组在等值查询和范围查询场景中的性能就都非常优秀。还是上面这个根据身份证号查名字的例子，如果我们使用有序数组来实现的话，示意图如下所示：

这里我们假设身份证号没有重复，这个数组就是按照身份证号递增的顺序保存的。这时候如果你要查 ID_card_n2 对应的名字，用二分法就可以快速得到，这个时间复杂度是 O(log(N))。

同时很显然，这个索引结构支持范围查询。你要查身份证号在 [ID_card_X, ID_card_Y] 区间的 User，可以先用二分法找到 ID_card_X（如果不存在 ID_card_X，就找到大于 ID_card_X 的第一个 User），然后向右遍历，直到查到第一个大于 ID_card_Y 的身份证号，退出循环。

如果仅仅看查询效率，有序数组就是最好的数据结构了。但是，在需要更新数据的时候就麻烦了，你往中间插入一个记录就必须得挪动后面所有的记录，成本太高。

所以，有序数组索引只适用于静态存储引擎，比如你要保存的是 2017 年某个城市的所有人口信息，这类不会再修改的数据。

二叉搜索树

还是上面根据身份证号查名字的例子，如果我们用二叉搜索树来实现的话，示意图如下所示：

二叉搜索树的特点是：每个节点的左儿子小于父节点，父节点又小于右儿子。这样如果你要查 ID_card_n2 的话，按照图中的搜索顺序就是按照 UserA ->UserC->UserF ->User2 这个路径得到。这个时间复杂度是 O(log(N))。

当然为了维持 O(log(N)) 的查询复杂度，你就需要保持这棵树是平衡二叉树。为了做这个保证，更新的时间复杂度也是 O(log(N))。

N 叉树

树可以有二叉，也可以有多叉。多叉树就是每个节点有多个儿子，儿子之间的大小保证从左到右递增。二叉树是搜索效率最高的，但是实际上大多数的数据库存储却并不使用二叉树。其原因是，索引不止存在内存中，还要写到磁盘上。

你可以想象一下一棵 100 万节点的平衡二叉树，树高 20。一次查询可能需要访问 20 个数据块。在机械硬盘时代，从磁盘随机读一个数据块需要 10ms 左右的寻址时间。也就是说，对于一个 100 万行的表，如果使用二叉树来存储，单独访问一个行可能需要 20 个 10ms 的时间，这个查询可真够慢的。

提示

B+ 树在机械硬盘和固态硬盘中，哪个效率更高？

B+树是一种常用的索引数据结构，用于在关系数据库管理系统中实现数据的快速查找。在机械硬盘（HDD）中，B+树的性能相对较低，主要是因为机械硬盘的磁盘寻址和旋转延迟会增加数据的访问时间。

然而，在固态硬盘（SSD）中，由于没有机械部件，数据的访问速度更快，而且随机访问的性能相对均匀。SSD 可以同时读取多个数据块，并且没有旋转延迟。这使得在SSD上使用B+树索引结构更加高效，因为它可以充分利用SSD的并行性和较低的访问延迟。

另外，SSD的特性也有助于减少磁盘碎片问题，因为SSD对随机写入的性能不敏感。这使得B+树索引在SSD上的维护和调整更加高效。

总结起来，由于固态硬盘的快速访问速度和较低的访问延迟，B+树在固态硬盘中的效率更高，能够提供更快的数据检索和索引维护操作。

为了让一个查询尽量少地读磁盘，就必须让查询过程访问尽量少的数据块。那么，我们就不应该 使用二叉树，而是要使用“N叉”树。这里，“N叉” 树中的 “N” 取决于数据块的大小。

以 InnoDB 的一个整数字段索引为例，这个 N 差不多是 1200。这棵树高是 4 的时候，就可以存 1200 的 3 次方个值，这已经 17亿了。考虑到树根的数据块总是在内存中的，一个 10 亿行的表上一个整数字段的索引，查找一个值最多只需要访问 3 次磁盘。其实，树的第二层也有很大概率在内存中，那么访问磁盘的平均次数就更少了。

N 叉树由于在读写上的性能优点，以及适配磁盘的访问模式，已经被广泛应用在数据库引擎中了。

InnoDB 中的索引

InnoDB存储引擎支持以下几种常见的索引：

• B+树索引
• 全文索引
• 哈希索引

InnoDB 存储引擎支持的哈希索引是自适应的，InnoDB 存储引擎会根据表的使用情况自动为表生成哈希索引，不能入为干预是否在一张表中生成哈希索引。

B+ 树索引就是传统意义上的索引，这是目前关系型数据库系统中查找最为常用和最为有效的索引。B+ 树索引的构造类似于二叉树，根据键值（Key Value）快速找到数据。

危险

但是注意：B+ 树索引并不能找到一个给定键值的具体行。B+ 树索引能找到的只是被查找数据行所在的页。然后数据库通过把页读入到内存，再在内存中进行查找，最后得到要查找的数据。

B+ 树的工作示例

每一个索引在 InnoDB 里面对应一棵 B+ 树。

假设，我们有一个主键列为 ID 的表，表中有字段 k，并且在 k 上有索引。这个表的建表语句是

create table T(
        id int primary key,
        k int not null,
        name varchar(16),
        index (k)
    ) engine = InnoDB;

表中 R1~R5 的 (ID,k) 值分别为 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6)，两棵树的示例示意图如下。

从图中不难看出，根据叶子节点的内容，索引类型分为主键索引和非主键索引。

主键索引的叶子节点存的是整行数据。在 InnoDB 里，主键索引也被称为聚簇索引（clustered index）。

非主键索引的叶子节点内容是主键的值。在InnoDB里，非主键索引也被称为二级索引（secondary index）。

根据上面的索引结构说明，我们来讨论一个问题：基于主键索引和普通索引的查询有什么区别？

聚集索引 VS 非聚集索引

在 MySQL 中，B+树索引按照存储方式的不同分为聚集索引和非聚集索引。（有些地方又称非聚集索引为二级索引）

提示

聚集索引就是主键索引，非聚集索引就是普通索引

数据库中的 B+ 树索引可以分为聚集索引（clustered index）和辅助索引（secondary index），但是不管是聚集还是辅助的索引，其内部都是 B+ 树的，即高度平衡的，叶子节点存放着所有的数据。

聚集索引与辅助索引不同的是，叶子节点存放的是否是一整行的信息。

示例：建表

create table T(
        id int primary key,
        k int not null,
        name varchar(16),
        index (k)
    ) engine = InnoDB;

id 字段是聚簇索引，k 字段是普通索引（二级索引）

非聚集索引与聚集索引的区别在于 非聚集索引的叶子节点不存储表中的数据，而是存储该列对应的主键，想要查找数据我们还需要根据主键再去聚集索引中进行查找，这个再根据聚集索引查找数据的过程，我们称为回表。

• 如果语句是 select * from T where ID = 500，即主键查询方式，则只需要搜索 ID 这棵 B+ 树；
• 如果语句是 select * from T where k = 5，即普通索引查询方式，则需要先搜索 k 索引树，得到 ID 的值为 500，再到 ID 索引树搜索一次。这个过程称为回表。

也就是说，基于非主键索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。

由于 InnoDB 存储引擎表是索引组织表，因此 InnoDB 存储引擎的辅助索引的书签就是相应行数据的聚集索引键。图 5-15 显示了 InnoDB 存储引擎中辅助索引与聚集索引的关系。

辅助索引的存在并不影响数据在聚集索引中的组织，因此每张表上可以有多个辅助索引。当通过辅助索引来寻找数据时，InnoDB 存储引擎会遍历辅助索引并通过叶级别的指针获得指向主键索引的主键，然后再通过主键索引来找到一个完整的行记录。

联合索引是什么？

后面要学习的最左前缀匹配原则：在 MySQL 建立联合索引时会遵守最左前缀匹配原则，即最左优先，在检索数据时从联合索引的最左边开始匹配。

要想理解联合索引的最左匹配原则，先来理解下索引的底层原理。索引的底层是一颗 B+ 树，那么联合索引的底层也就是一颗 B+ 树，只不过联合索引的 B+ 树节点中存储的是键值。由于构建一棵 B+ 树只能根据一个值来确定索引关系，所以数据库依赖联合索引最左的字段来构建。

举例：创建一个（a,b）的联合索引，那么它的索引树就是下图的样子。

可以看到 a 的值是有顺序的，1，1，2，2，3，3，而 b 的值是没有顺序的 1，2，1，4，1，2。

但是我们又可发现 a 在等值的情况下，b 值又是按顺序排列的，但是这种顺序是相对的。这是因为 MySQL 创建联合索引的规则是首先会对联合索引的最左边第一个字段排序，在第一个字段的排序基础上，然后在对第二个字段进行排序。

所以 b = 2 这种查询条件没有办法利用索引。

索引维护

B+ 树为了维护索引有序性，在插入新值的时候需要做必要的维护。以上面这个图为例，如果插入新的行 ID 值为 700，则只需要在 R5 的记录后面插入一个新记录。如果新插入的 ID 值为 400，就相对麻烦了，需要逻辑上挪动后面的数据，空出位置。

而更糟的情况是，如果 R5 所在的数据页已经满了，根据 B+ 树的算法，这时候需要申请一个新的数据页，然后挪动部分数据过去。这个过程称为页分裂。在这种情况下，性能自然会受影响。

除了性能外，页分裂操作还影响数据页的利用率。原本放在一个页的数据，现在分到两个页中，整体空间利用率降低大约 50%。

当然有分裂就有合并。当相邻两个页由于删除了数据，利用率很低之后，会将数据页做合并。合并的过程，可以认为是分裂过程的逆过程。

基于上面的索引维护过程说明，我们来讨论一个案例：

你可能在一些建表规范里面见到过类似的描述，要求建表语句里一定要有自增主键。当然事无绝对，我们来分析一下哪些场景下应该使用自增主键，而哪些场景下不应该。

自增主键是指自增列上定义的主键，在建表语句中一般是这么定义的： NOTNULL PRIMARY KEY AUTO_INCREMENT。

插入新记录的时候可以不指定 ID 的值，系统会获取当前 ID 最大值加 1 作为下一条记录的 ID 值。

也就是说，自增主键的插入数据模式，正符合了我们前面提到的递增插入的场景。每次插入一条新记录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂。

而有业务逻辑的字段做主键，则往往不容易保证有序插入，这样写数据成本相对较高。

除了考虑性能外，我们还可以从存储空间的角度来看。假设你的表中确实有一个唯一字段，比如字符串类型的身份证号，那应该用身份证号做主键，还是用自增字段做主键呢？

由于每个非主键索引的叶子节点上都是主键的值。如果用身份证号做主键，那么每个二级索引的叶子节点占用约 20 个字节，而如果用整型做主键，则只要 4 个字节，如果是长整型（bigint）则是 8 个字节。

显然，主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。

所以，从性能和存储空间方面考量，自增主键往往是更合理的选择。

有没有什么场景适合用业务字段直接做主键的呢？还是有的。比如，有些业务的场景需求是这样的：

1. 只有一个索引；
2. 该索引必须是唯一索引。

你一定看出来了，这就是典型的 K-V 场景。

由于没有其他索引，所以也就不用考虑其他索引的叶子节点大小的问题。这时候我们就要优先考虑上一段提到的 “尽量使用主键查询” 原则，直接将这个索引设置为主键，可以避免每次查询需要搜索两棵树。

数据结构和算法

这里先介绍 InnoDB 用到的数据结构和算法，以便后续的学习，下面沿着为什么要使用 B+ 树索引来展开讲解。

二分查找算法

每页 Page Directory 中的槽是按照主键的顺序存放的，对于某一条具体记录的查询是通过对 Page Directory 进行二分查找得到的。

二叉查找树

二叉查找树的特点就是任何节点的左子节点的键值都小于当前节点的键值，右子节点的键值都大于当前节点的键值。 顶端的节点我们称为根节点，没有子节点的节点我们称之为叶节点。

首先，让我们先看一张图

从图中可以看到，我们为 user表（用户信息表）建立了一个二叉查找树的索引。图中的圆为二叉查找树的节点，节点中存储了键（key）和数据（data）。

这里创建一个索引

CREATE INDEX index_name ON table_name (column_name)

键对应 user 表中的 id，数据对应 user 表中的行数据。

如果我们需要查找 id=12 的用户信息，利用我们创建的二叉查找树索引，查找流程如下：

1. 将根节点作为当前节点，把 12 与当前节点的键值10比较，12大于10，接下来我们把当前节点>的右子节点作为当前节点。
2. 继续把12和当前节点的键值13比较，发现12小于13，把当前节点的左子节点作为当前节点。
3. 把12和当前节点的键值12对比，12等于12，满足条件，我们从当前节点中取出data，即 id=12,name=xm。

利用二叉查找树我们只需要3次即可找到匹配的数据。如果在表中一条条的查找的话，我们需要6次才能找到。

但是，如果上面的二叉查找树是这样的构造：

这个时候可以看到我们的二叉查找树变成了一个链表。

如果我们需要查找 id=17 的用户信息，我们需要查找7次，也就相当于全表扫描了。

导致这个现象的原因其实是 二叉查找树变得不平衡了，也就是高度太高了，从而导致查找效率的不稳定。

为了解决这个问题，我们需要保证二叉查找树一直保持平衡，就需要用到平衡二叉树了。

平衡二叉树

注：这里就跳过红黑树了，因为它单纯只是平衡二叉树的改进版，其缺点和这个 AVL树是一样的

平衡二叉树又称AVL树，在满足二叉查找树特性的基础上，要求每个节点的左右子树的高度差不能超过 1。

下面是平衡二叉树和非平衡二叉树的对比：

平衡二叉树保证了树的构造是平衡的，当我们插入或删除数据导致不满足平衡二叉树不平衡时，平衡二叉树会进行调整树上的节点来保持平衡。具体的调整方式这里就不介绍了。

平衡二叉树相比于二叉查找树来说，查找效率更稳定，总体的查找速度也更快。

但是如果用平衡二叉树这种数据结构作为索引的数据结构，那我们每查找一次数据就需要从磁盘中读取一个节点，也就是我们说的一个磁盘块，平衡二叉树可是每个节点只存储一个键值和数据的。

那说明什么？

说明每个磁盘块仅仅存储一个键值和数据！

那如果我们要存储海量的数据呢？

可以想象到二叉树的节点将会非常多，高度也会及其高，我们查找数据时也会进行很多次磁盘IO，我们查找数据的效率将会极低！

所以缺点：无论是二叉树还是红黑树，都会因为树的深度过深而造成 IO 次数变多，影响数据读取的效率

为了解决平衡二叉树的这个弊端，我们应该寻找 一种单个节点可以存储多个键值和数据的平衡树。也就是我们接下来要说的B树。

B 树的结构

B树（Balance Tree）即为平衡树的意思。

它的每个节点都为页（在 MySQL 中数据读取的基本单位都是页）

B树特点：

1. 所有键值分布在整颗树中
2. 搜索有可能在非叶子结点结束，在关键字全集内做一次查找，性能逼近分查找
3. 每个节点最多拥有 m 个子树
4. 根节点至少有 2 个子树
5. 分支节点至少拥有 $m / 2$ 颗子树（除根节点和叶子节点外都是分支节点）
6. 所有叶子节点都在同一层、每个节点最多可以有 $m-1$ 个 key，并且以升序排列

B树相对于平衡二叉树，每个节点存储了更多的键值（key）和数据（data），并且每个节点拥有更多的子节点，子节点的个数一般称为阶，上述图中的 B树为 3阶 B树，高度也会很低。

基于这个特性，B 树查找数据读取磁盘的次数将会很少，数据的查找效率也会比平衡二叉树高很多（因为每个节点都是一个页，所以 B 树节点内采用的是二分查找）。

但是 B 树还是有缺点的：

因为每个节点都有 key，同时也包含 data，而每个页存储空间是有限的，如果 data 比较大的话会导致每个节点存储的 key 数量变小，所以当存储的数据量很大的时候会导致深度较大，增大查询时磁盘 IO 次数。进而影响查询性能

B+ 树的结构

B+ 树 是在 B 树的基础之上做的一种优化，让我们先来看下 B+ 树的结构图：

先来看看它与 B 树的区别，以及这样做的好处：

B+ 树非叶子节点上是不存储数据的，仅存储键值，而 B 树节点中不仅存储键值，也会存储数据。

之所以这么做是因为在数据库中页的大小是固定的，InnoDB 中页的默认大小是 16KB。如果不存储数据，那么就会存储更多的键值，相应的树的阶数（节点的子节点树）就会更小，树就会更矮更胖，如此一来我们查找数据进行磁盘的 IO 次数有会再次减少，数据查询的效率也会更快。

另外，B+ 树的阶数是等于键值的数量的，如果我们的 B+ 树一个节点可以存储 1000 个键值，那么 3 层 B+ 树可以存储1000×1000×1000=10亿个数据。一般根节点是常驻内存的，所以一般我们查找 10亿数据，只需要 2次磁盘 IO。

在 B+Tree 上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。因此可以对 B+Tree 进行两种查找运算：一种是对于主键的范围查找和分页查找，另一种是从根节点开始，进行随机查找。

因为 B+ 树索引的所有数据均存储在叶子节点，而且数据是按照顺序排列的。那么 B+ 树使得范围查找，排序查找，分组查找以及去重查找变得异常简单。而 B 树因为数据分散在各个节点，要实现这一点是很不容易的。

而且 B+ 树中各个页之间是通过双向链表连接的，叶子节点中的数据是通过单向链表连接的。

注意：MyISAM 中的 B+ 树索引实现与 InnoDB 中的略有不同。在 MyISAM 中，B+ 树索引的叶子节点并不存储数据，而是存储数据的文件地址。（具体看下面）

B+ 树的链表为啥是双向的？

MySQL的B+树的链表通常是双向链表。如下图所示

在MySQL中，B+树被广泛用于索引数据结构，特别是在InnoDB存储引擎中。B+树的叶子节点存储了实际的数据行，并且这些叶子节点通常形成一个双向链表。

双向链表的特点是每个节点都包含一个指向前一个节点和后一个节点的指针，使得可以在节点之间进行前向和后向遍历。这在数据库系统中是非常有用的，因为可以支持范围查询、排序和迭代等操作。

通过使用双向链表，MySQL可以实现以下功能：

1. 范围查询：B+树的双向链表可以通过指针在叶子节点之间进行前向和后向遍历，从而支持范围查询操作。例如，可以从某个节点开始，沿着双向链表遍历到下一个节点，并获取范围内的数据行。

2. 排序：B+树的双向链表可以按照特定的顺序遍历节点，使得可以对数据行进行排序操作。例如，可以从树的最左边的叶子节点开始遍历，按顺序获取数据行，实现有序的查询结果。

3. 迭代：B+树的双向链表可以支持快速的迭代操作。通过使用前向和后向指针，可以在节点之间高效地移动，并处理每个节点的数据行。

需要注意的是，双向链表在B+树的内部节点通常不是必需的，因为内部节点主要用于索引导航而不存储实际的数据行。而叶子节点才是存储数据行的节点，因此双向链表主要是在叶子节点上实现的。

综上所述，MySQL的B+树的链表通常是双向链表，用于支持范围查询、排序和迭代等操作。

B+ 树的插入操作

B+ 树的插入必须保证插入后叶子节点中的记录依然排序，同时需要考虑插入到 B+ 树的三种情况，每种情况都可能会导致不同的插入算法。

这里用一个例子来分析 B+ 树的插入。例如，对于图 5-6 中的这棵 B+ 树，若用户插入 28 这个键值，发现当前 LeafPage 和 Index Page 都没有满，直接进行插入即可，之后得到图 5-7

接着再插入 70 这个键值，这时原先的 Leaf Page 已经满了，但是 Index Page 还没有满，符合表的第二种情况，这时插入 Leaf Page 后的情况为 55、55、60、65、70，并根据中间的值 60 来拆分叶子节点，可得图 5-8。

注意：因为图片显示的关系，这次没有能在各叶子节点加上双向链表指针。不过和图 5-6 图 5-7 一样，它还是存在的。

最后插入键值 95，这时符合表中讨论的第三种情况，即 Leaf Page 和 Index Page 都满了，这时需要做两次拆分，如图 5-9 所示。

可以看到，不管怎么变化，B+ 树总是会保持平衡。

但是为了保持平衡对于新插人的键值可能需要做大量的拆分页（split）操作。因为 B+ 树结构主要用于磁盘，页的拆分意味着磁盘的操作，所以应该在可能的情况下尽量减少页的拆分操作。

因此，B+ 树同样提供了类似于平衡二叉树的旋转（Rotation）功能（其实就是重新挪位置）。

旋转发生在 Leaf Page 已经满，但是其的 左右兄弟节点 没有满的情况下。这时 B+ 树并不会急于去做拆分页的操作，而是将记录移到所在页的兄弟节点上。

在通常情况下，左兄弟会被首先检查用来做旋转操作，因此再来看图 5-7 的情况，若插人键值 70，其实 B+ 树并不会急于去拆分叶子节点，而是去做旋转操作，得到如图 5-10 所示的操作。

从图 5-10 可以看到，采用旋转操作使 B+ 树减少了一次页的拆分操作，同时这棵 B+ 树的高度依然还是 2。

B+ 树的删除操作

B+ 树使用填充因子（fillfactor）来控制树的删除变化，50% 是填充因子可设的最小值。

B+ 树的删除操作同样必须保证删除后叶子节点中的记录依然排序，同插入一样，B+ 树的删除操作同样需要考虑以下表5-2中的三种情况，与插入不同的是，删除根据填充因子的变化来衡量。

根据图 5-9 的 B+ 树来进行删除操作。首先删除键值为 70 的这条记录，该记录符合表 5-2 讨论的第一种情况，删除后可得到图 5-11

接着删除键值为 25 的记录，这也是表 5-2 讨论的第一种情况，但是该值还是 Index Page 中的值，因此在删除 LeafPage 中的 25 后，还应将 25 的右兄弟节点的 28 更新到 Page Index中，最后可得图 5-12。

最后看删除键值为 60 的情况。删除 Leaf Page 中键值为 60 的记录后，Fill Factor 小于 50%，这时需要做合并操作，同样，在删除 Index Page 中相关记录后需要做 Index Page 的合并操作，最后得到图 5-13。

补充：InnoDB 和 MyISAM 的 B+树

InnoDB 和 MyISAM 的 B+树实现是有一点区别的

InnoDB 的结构

对应的 B+ 树索引：

注意：在 InnoDB 存储引擎中，表都是根据主键顺序组织存放的，这种存储方式的表称为索引组织表（index organized table）。在 InnoDB 存储引擎表中，每张表都有个主键（Primary Key）。因此 数据即索引，索引即数据。

如果在创建表时没有显式地定义主键，则 InnoDB 存储引擎会按如下方式选择或创建主键：

• 首先判断表中是否有非空的唯一索引（Unique NOT NULL），如果有，则该列即为主键。
• 如果不符合上述条件，InnoDB 存储引擎自动创建一个 6 字节大小的指针。

当表中有多个非空唯一索引时， InnoDB 存储引擎将选择建表时第一个定义的非空唯一索引为主键。这里需要非常注意的是，主键的选择根据的是定义索引的顺序，而不是建表时列的顺序。

这块具体看 InnoDB 表空间那篇笔记~

MyISAM 的结构

在 MyISAM中，B+树索引的叶子节点并不存储数据，而是存储数据的文件地址。因为在 MyISAM 中，索引和数据文件是分开存储的

Reference

• MySQL 45讲